/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：SplayTree.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-03-29
Function List ：
Description   ：Splay Tree(Top-down)
******************************************************/

#include "SplayTree.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"
#include "LinkedStack.h"
#include "LinkedQueue.h"

#define Infinity    (32767)   // 2^16-1
#define NegInfinity (-32768)  // -2^16

struct SplayNode {
    ElementType Element;
    SplayTree   Left;
    SplayTree   Right;
};

// Static Function Lists
static SplayTree Splay(ElementType X, SplayTree T);
static Position SingleRotateWithLeft(Position K2);
static Position SingleRotateWithRight(Position K1);

// Global Variable Lists
Position NullNode = NULL;  /* Needs initialization */

SplayTree Initialize(void) {
    if (NullNode == NULL) {
        NullNode = (SplayTree)malloc(sizeof(struct SplayNode));
        if (NullNode == NULL) {
            FatalError("Out of space!!!");
        }

        NullNode->Left = NullNode;
        NullNode->Right = NullNode;
    }

    return NullNode;
}

SplayTree MakeEmpty(SplayTree T) {
    if (T != NullNode) {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }

    return NullNode;
}

int IsEmpty(SplayTree T) {
    return (T == NULL) || (T == NullNode);
}

Position Find(ElementType X, SplayTree T) {
    return Splay(X, T);
}

Position FindMin(SplayTree T) {
    return Splay(NegInfinity, T);
}

Position FindMax(SplayTree T) {
    return Splay(Infinity, T);
}

/* Top-down splay procedure */
/* not requiring Item to be in the tree */
static SplayTree Splay(ElementType X, SplayTree T) {
    static struct SplayNode Header;
    Position LeftTreeMax;
    Position RightTreeMin;

    Header.Left = NullNode;
    Header.Right = NullNode;
    LeftTreeMax = &Header;
    RightTreeMin = &Header;
    NullNode->Element = X;

    while (X != T->Element) {
        if (X < T->Element) {
            if (X < T->Left->Element) {
                T = SingleRotateWithLeft(T);
            }

            if (T->Left == NullNode) {
                break;
            }

            /* Link right */
            RightTreeMin->Left = T;
            RightTreeMin = T;
            T = T->Left;
        } else {
            if (X > T->Right->Element) {
                T = SingleRotateWithRight(T);
            }

            if (T->Right == NullNode) {
                break;
            }

            /* Link left */
            LeftTreeMax->Right = T;
            LeftTreeMax = T;
            T = T->Right;
        }
    }  /* while (X != T->Element) */

    /* Reassemble */
    LeftTreeMax->Right = T->Left;
    RightTreeMin->Left = T->Right;
    T->Left = Header.Right;
    T->Right = Header.Left;

    return T;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
static Position SingleRotateWithLeft(Position K2) {
    Position K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    return K1;  /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */
static Position SingleRotateWithRight(Position K1) {
    Position K2;

    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;

    return K2;  /* New root */
}

SplayTree Insert(ElementType X, SplayTree T) {
    static Position NewNode = NULL;

    if (NewNode == NULL) {
        NewNode = (SplayTree)malloc(sizeof(struct SplayNode));
        if (NewNode == NULL) {
            FatalError("Out of space!!!");
        }
    }

    NewNode->Element = X;

    if (T == NullNode) {
        NewNode->Left = NullNode;
        NewNode->Right = NullNode;
        T = NewNode;
    } else {
        T = Splay(X, T);
        if (X < T->Element) {
            NewNode->Left = T->Left;
            NewNode->Right = T;
            T->Left = NullNode;
            T = NewNode;
        } else if (X > T->Element) {
            NewNode->Right = T->Right;
            NewNode->Left = T;
            T->Right = NullNode;
            T = NewNode;
        } else {
            return T;  /* Already in the tree */
        }
    }

    NewNode = NULL;  /* So next insert will call malloc */
    return T;  /* Do not forget this line!! */
}

SplayTree Remove(ElementType X, SplayTree T) {
    Position NewTree;

    if (T != NullNode) {
        T = Splay(X, T);
        /* Found it! */
        if (X == T->Element) {
            if (T->Left == NullNode) {
                NewTree = T->Right;
            } else {
                NewTree = T->Left;
                NewTree = Splay(X, NewTree);
                NewTree->Right = T->Right;
            }

            free(T);
            T = NewTree;
        }
    }

    return T;
}

Position Left(Position P) {
    return P->Left;
}

Position Right(Position P) {
    return P->Right;
}

ElementType Retrieve(Position P) {
    return P->Element;
}

// Recursive implement
// void PreorderTraversal(SplayTree T) {
//     if (T != NullNode) {
//         printf("%d ", T->Element);
//         PreorderTraversal(T->Left);
//         PreorderTraversal(T->Right);
//     }
// }

// Non-recursive implement
void PreorderTraversal(SplayTree T) {
    if (T != NullNode) {
        LinkedStack S;
        Position P;

        S = CreateStack();

        P = T;
        while (P != NullNode || !IsEmptyStack(S)) {
            while (P != NullNode) {
                printf("%d ", P->Element);
                Push(P, S);
                P = P->Left;
            }

            P = TopAndPop(S);
            P = P->Right;
        }
    }
}

// Recursive implement
// void InorderTraversal(SplayTree T) {
//     if (T != NullNode) {
//         InorderTraversal(T->Left);
//         printf("%d ", T->Element);
//         InorderTraversal(T->Right);
//     }
// }

// Non-recursive implement
void InorderTraversal(SplayTree T) {
    if (T != NullNode) {
        LinkedStack S;
        Position P;

        S = CreateStack();

        P = T;
        while (P != NullNode || !IsEmptyStack(S)) {
            while (P != NullNode) {
                Push(P, S);
                P = P->Left;
            }

            P = TopAndPop(S);
            printf("%d ", P->Element);
            P = P->Right;
        }
    }
}

// Recursive implement
// void PostorderTraversal(SplayTree T) {
//     if (T != NullNode) {
//         PostorderTraversal(T->Left);
//         PostorderTraversal(T->Right);
//         printf("%d ", T->Element);
//     }
// }

// Non-recursive implement
void PostorderTraversal(SplayTree T) {
    if (T != NullNode) {
        LinkedStack S;
        Position Pre;
        Position Cur;

        S = CreateStack();

        Cur = T;
        Pre = NullNode;
        while (Cur != NullNode || !IsEmptyStack(S)) {
            if (Cur != NullNode) {
                Push(Cur, S);
                Cur = Cur->Left;
            } else {
                Cur = Top(S);
                if (Cur->Right != NullNode && Cur->Right != Pre) {
                    Cur = Cur->Right;
                } else {
                    Pop(S);
                    printf("%d ", Cur->Element);
                    Pre = Cur;
                    Cur = NullNode;
                }
            }
        }
    }
}

void LevelorderTraversal(SplayTree T) {
    if (T != NullNode) {
        LinkedQueue Q;

        Q = CreateQueue();

        EnQueue(T, Q);

        while (!IsEmptyQueue(Q)) {
            if (Front(Q)->Left != NullNode) {
                EnQueue(Front(Q)->Left, Q);
            }

            if (Front(Q)->Right != NullNode) {
                EnQueue(Front(Q)->Right, Q);
            }

            printf("%d ", Retrieve(FrontAndDequeue(Q)));
        }
    }
}

// EOF

